package org.laizili.solution.leetcode;

import java.util.Arrays;
import java.util.Random;

/**
 * <a href="https://leetcode.cn/problems/matchsticks-to-square/">473. 火柴拼正方形</a>
 * <p>
 * tags: 回溯+剪枝; 转态压缩+动态规划
 */
public class Problem473 {
    private static class Solution {
        public boolean makesquare(int[] matchsticks) {
            if (matchsticks.length < 4) {
                return false;
            }
            int sum = 0;
            for (int matchstick : matchsticks) {
                sum += matchstick;
            }
            if (sum % 4 != 0) {
                return false;
            }
            // 排序: 减少搜索，这个没考虑到
            Arrays.sort(matchsticks);
            int mid = matchsticks.length / 2;
            for (int i = 0, j = matchsticks.length - 1; i < mid; i++, j--) {
                int tmp = matchsticks[i];
                matchsticks[i] = matchsticks[j];
                matchsticks[j] = tmp;
            }
            return backtrace(matchsticks, 0, sum / 4, new int[4]);
        }

        private boolean backtrace(int[] matchsticks, int stickIndex, int expected, int[] sideLength) {
            if (stickIndex >= matchsticks.length) {
//                能分配完所有的火柴肯定就满足条件了
//                因为: 前面已经判断过火柴总长度是4的倍数
/*                for (int len : sideLength) {
                    if (expected != len) {
                        return false;
                    }
                }*/
                return true;
            }
            for (int i = 0; i < 4; i++) {
                int matchstick = matchsticks[stickIndex];
                sideLength[i] += matchstick;
                if (sideLength[i] <= expected /*这个剪枝条件没有考虑到*/ && backtrace(matchsticks, stickIndex + 1, expected, sideLength)) {
                    return true;
                }
                sideLength[i] -= matchstick;
            }
            return false;
        }
    }
    // TODO: 动态规划解法

    // 模拟退火
    private static class Solution3 {
        int[] ms;
        int n, k;
        Random random = new Random(20220601);
        boolean ans = false;
        double hi = 1e4, lo = 1e-4, fa = 0.98;
        int N = 400;

        int calc() {
            int diff = 0;
            for (int i = 0, j = 0; i < 4; i++) {
                int cnt = 0;
                while (j < n && cnt < k) cnt += ms[j++];
                diff += Math.abs(cnt - k);
            }
            if (diff == 0) ans = true;
            return diff;
        }

        void sa() {
            for (double t = hi; t > lo && !ans; t *= fa) {
                int a = random.nextInt(n), b = random.nextInt(n);
                int prev = calc();
                swap(ms, a, b);
                int cur = calc();
                int diff = prev - cur;
                if (Math.log(diff / t) > random.nextDouble()) swap(ms, a, b);
            }
        }

        public boolean makesquare(int[] _ms) {
            ms = _ms;
            n = ms.length;
            int sum = 0;
            for (int i : ms) sum += i;
            k = sum / 4;
            if (k * 4 != sum) return false;
            shuffle(ms);
            while (N-- > 0) sa();
            return ans;
        }

        void shuffle(int[] arr) {
            int n = arr.length;
            for (int i = n; i > 0; i--) {
                int idx = random.nextInt(i);
                swap(arr, idx, i - 1);
            }
        }

        void swap(int[] arr, int i, int j) {
            int c = arr[i];
            arr[i] = arr[j];
            arr[j] = c;
        }
    }


    public static void main(String[] args) {
        System.out.println(new Solution().makesquare(new int[]{
                5969561, 8742425, 2513572, 3352059, 9084275, 2194427, 1017540, 2324577,
                6810719, 8936380, 7868365, 2755770, 9954463, 9912280, 4713511}));
    }
}
